# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Node:
    def __init__(self, node):
        self.val = node.val
        self.left = Node(node.left) if node.left else None
        self.right = Node(node.right) if node.right else None
        self.size = 1

    def calcSize(self):
        self.size += self.left.calcSize() if self.left else 0
        self.size += self.right.calcSize() if self.right else 0
        return self.size
    
    def find(self, k):
        if self.size<k: return None
        if self.left == None:
            if k==1: return self.val
            else: return self.right.find(k-1)
        elif k<=self.left.size:
            return self.left.find(k)
        elif k==self.left.size+1:
            return self.val
        else:
            return self.right.find(k-self.left.size-1)

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        root = Node(root)
        root.calcSize()
        return root.find(k)

root = TreeNode(1)
print(Solution().kthSmallest(root, 1))